package com.wlr.study.leetcode;

import java.util.*;

/**
 * @author lrwang
 * @version 1.0
 * @date 2021/6/30 22:21
 */
public class Solution {
    //    输入：n = 3
//    输出：["((()))","(()())","(())()","()(())","()()()"]
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<String>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {//4
            if (valid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    public boolean valid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        if (nums.length <= 0) {
            result[0] = result[1] = -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < nums.length && right > 0) {
            if (nums[left] != target) {
                left++;
            } else {
                result[0] = left;
            }
            if (nums[right] != target) {
                right--;
            } else {
                result[1] = right;
            }
        }
        if (left == nums.length - 1 && right == 0) {
            result[0] = result[1] = -1;
        }
        return result;
    }

    /**
     * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     *
     * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     * 输入：nums = [2,0,2,1,1,0]
     * 输出：[0,0,1,1,2,2]
     * @param nums
     */
//    public void sortColors(int[] nums) {
//        int num0 = 0, num1 = 0, num2 = 0;
//        for(int i = 0; i < nums.length; i++) {
//            if(nums[i] == 0) {
//                nums[num2++] = 2;
//                nums[num1++] = 1;
//                nums[num0++] = 0;
//            }else if(nums[i] == 1) {
//                nums[num2++] = 2;
//                nums[num1++] = 1;
//            }else {
//                nums[num2++] = 2;
//            }
//        }
//    }

    /**
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     *
     * @param s
     * @param t
     * @return
     */
//    public String minWindow(String s, String t) {
//        int length=0,count=0;
//        for (int i=0;i<s.length();i++){
//            for (int j=0;j<t.length();j++){
//                if (s.charAt(i))
//            }
//        }
//        return null;
//    }

    /**
     * 上下翻转二叉树
     *
     * @param root 根节点
     * @return 翻转后的二叉树
     */
    public static TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == null) {
            return root;
        }
        TreeNode LE = root.left, RI = root.right;
        TreeNode res = upsideDownBinaryTree(root.left);
        root.left = null;
        root.right = null;
        LE.right = root;
        LE.left = RI;
        return res;
    }

    public static int countValidWords(String sentence) {
        String[] secondArr = sentence.split(" ");
        int count = 0;
        for (String str : secondArr) {
            if (str.length() > 0) {
                if (str.matches("^(([a-z]+[-]?[a-z]+)|([a-z]*))[!.,]?$")) {
                    System.out.println(str);
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 字符串最长字串
     *
     * @param s 传参
     * @return 长度
     */
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }

    /**
     * 数组中位数
     *
     * @param nums1 数组1
     * @param nums2 数组2
     * @return 中位数
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] newArr = new int[nums1.length + nums2.length];
        int j = 0;
        for (int i = 0; i < nums1.length; i++) {
            newArr[i] = nums1[i];
        }
        for (int i = nums1.length; i < newArr.length; i++) {
            newArr[i] = nums2[j];
            j++;
        }
        Arrays.sort(newArr);
        double mid = 0.00;
        if (newArr.length % 2 == 0) {
            int left = newArr.length / 2 - 1;
            int right = newArr.length / 2;
            mid = (double) (newArr[left] + newArr[right]) / 2;
        } else {
            mid = newArr[newArr.length / 2];
        }
        return mid;
    }

    /**
     * 中位数另一种解法
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    //i: nums1的起始位置 j: nums2的起始位置
    public int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) {
            return nums2[j + k - 1];
        }//nums1为空数组
        if (j >= nums2.length) {
            return nums1[i + k - 1];
        }//nums2为空数组
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }

    /**
     * 最长回文子串
     *
     * @param s 字符串
     * @return 最长回文子串
     */
    public String longestPalindrome(String s) {
        // 记录最长回文串
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            // 当回文串是奇数时，由一个中心点向两边扩散
            String s1 = palindrome(s, i, i);
            // 当回文串是偶数时，由中间的两个中心点向两边扩散
            String s2 = palindrome(s, i, i + 1);

            // 三元运算符：判断为真时取冒号前面的值，为假时取冒号后面的值
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    // 辅助函数：寻找回文串
    private String palindrome(String s, int left, int right) {
        // 在区间 [0, s.length() - 1] 中寻找回文串，防止下标越界
        while (left >= 0 && right < s.length()) {
            // 是回文串时，继续向两边扩散
            if (s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } else {
                break;
            }
        }
        // 循环结束时的条件是 s.charAt(left) != s.charAt(right), 所以正确的区间为 [left + 1, right), 方法 substring(start, end) 区间是 [start, end), 不包含 end
        return s.substring(left + 1, right);
    }

    /**
     * Z字形变换
     *
     * @param s       字符串
     * @param numRows 行数
     * @return 变换后的字符串
     */
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuffer[] sbs = new StringBuffer[numRows];
        for (int i = 0; i < numRows; i++) {
            sbs[i] = new StringBuffer();
        }
        int flag = 1;
        int n = 0;
        for (int i = 0; i < s.length(); i++) {
            sbs[n].append(s.charAt(i));
            if (n == 0 || n == numRows - 1) {
                flag = flag == 0 ? 1 : 0;
            }
            if (flag == 0) {
                n++;
            } else {
                n--;
            }

        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < numRows; i++) {
            sb.append(sbs[i].toString());
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String sentence = "babad";
        System.out.println(solution.lengthOfLongestSubstring(sentence));
        int[] nums1 = {1, 2}, nums2 = {3, 4};
        System.out.println(solution.findMedianSortedArrays(nums1, nums2));
        System.out.println(solution.findMedianSortedArrays1(nums1, nums2));
        //System.out.println("stone-game10".contains(1+""));
        System.out.println(solution.convert("PAYPALISHIRING",4));
    }
}
